/**
 * Created by zhangjinrui on 17/6/27.
 */

public class Solution96 {

    public static void main(String args[]) {
        Solution96 s = new Solution96();
        System.out.println(s.numTrees(4));
    }

    public int numTrees(int n) {
        int[] mp = new int[n + 1];
        mp[0] = 1;
        return dfs(n, mp);
    }

    public int dfs(int n, int[] mp) {
//        if (n == 0 || n == 1) {
//            return 1;
//        }
        if (mp[n] != 0) {
            return mp[n];
        }
        n--;
        int sum = 0;
        for (int i = 0; i <= n; i++) {
            int l = dfs(i, mp);
            int r = dfs(n - i, mp);
            sum += l * r;
        }
        mp[n + 1] = sum;
        return sum;
    }
}
